package aloge;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class QuickSort {

    public List<Integer> sort(List<Integer> numbers) {
        return sort(numbers, 0, numbers.size() - 1);
    }

    private List<Integer> sort(List<Integer> numbers, int start, int end) {
        while (start < end) {
            int split = split(numbers, start, end);
            sort(numbers, start, split - 1);
            start = split + 1;
        }
        return numbers;
    }

    private int split(List<Integer> numbers, int start, int end) {
        int x = numbers.get(end);
        int i = start - 1;
        for (int j = start; j < end; j++) {
            if (numbers.get(j) < x) {
                // 切换
                i = i + 1;
                int num = numbers.get(j);
                numbers.set(j, numbers.get(i));
                numbers.set(i, num);
            }
        }
        numbers.set(end, numbers.get(i + 1));
        numbers.set(i + 1, x);
        return i + 1;
    }

    public static void main(String[] args) {
        ArrayList<Integer> integers = new ArrayList<>(List.of(1, 3, 7, 8, 2, 4, 5));
        List<Integer> sort = new QuickSort().sort(integers);
        System.out.println(sort);
    }

}
